// 
// A Cache class.
//
//

#include "CPU.h"
#include "base/Entity.h"
#include "base/LoadRequest.h"
#include "base/Packet.h"
#include "base/QuiesceRequest.h"
#include "base/QuiesceResponse.h"
#include "base/RawFlushRequest.h"
#include "base/Response.h"
#include "base/Simulator.h"
#include "base/SnoopResponse.h"
#include "base/StoreRequest.h"
#include "mem/Cache.h"
#include "mem/CacheHash.h"
#include "mem/InvalidateRequest.h"
#include "mem/UpdateRequest.h"
#include "mem/VerifyRequest.h"
#include "mem/CancelRequestsRequest.h"
#include "mem/RawMemoryRequest.h"

NEW_DELETE_OPERATORS_CPP(Cache,1);

NEW_DELETE_OPERATORS_TEMPLATE_CPP(List<CacheEntry*>, 10);
NEW_DELETE_OPERATORS_TEMPLATE_CPP(__quote__(HashTable<VA, CacheEntry*>), 10);
NEW_DELETE_OPERATORS_TEMPLATE_CPP(__quote__(HashTableNode<VA, CacheEntry*>), 1000000);
NEW_DELETE_OPERATORS_TEMPLATE_CPP(List<VA>, 10);

Cache::Cache (const char* _name,
              uint    _size,
              uint    _blockSize,
              uint    _assoc,
              uint    _vcsize,
              uint    _delay,
              uint    _maxMSHRs,
              LineFlags const* _protoFlags,
              Counter* _statAccesses,
              Counter* _statHits,
              Counter* _statMisses,
              Bucket* _bktNextLvlStall,
              Bucket* _bktUnavailable)
:
    Entity(_name, CLOCK_FIRST),
    size(_size),
    blockSize(_blockSize),
    assoc(_assoc),
    delay(_delay),
    maxMSHRs(_maxMSHRs),
    reservedVCs(0),
    cacheLog(NEW Logger("cacheLog", "c", "-:w,log.sim", "Cache tracing", this)),
    hash(NEW CacheHash(this, cacheLog, size, blockSize, assoc, _vcsize)),
    protoFlags(_protoFlags),
    lg2BlockSize((int)log2(blockSize)),
    lg2Assoc((int)log2(assoc)),
    indexShift(lg2BlockSize),
    indexMask((size / blockSize - 1) >> lg2Assoc),
    tagShift(indexShift +
             (uint)log2(size / blockSize) -
             lg2Assoc),
    quiesce(false),
    quiesceRequest(NULL),
    lastAccessClock(0),
    agingDataRequests(NEW List<PacketDelay*>),
    mshrs(NEW List<MSHR*>),
    canceledLoadRequests(NEW List<LoadRequest*>),
    stalledLoad(NULL),
    blockedLoad(NULL),
    blockedLoadTime(0),
    blockedTimeouts(0),
    stalledEvict(NULL),
    stalledSnoopResponse(NEW List<SnoopResponse*>),
    pendingResponse(NEW List<Response*>),
    outstandingEvicts(0),
    statAccesses(_statAccesses),
    statHits(_statHits),
    statMisses(_statMisses),
    bktStall(_bktNextLvlStall),
    bktUnavailable(_bktUnavailable),
    lastRawFlushTime(0),
    lastRawFlushStart(0),
    lastRawFlushLength(0)
{
    registerPacketHandler(typeid(LoadRequest),
                         (PacketHandlerPtr)&Cache::handle_DataRequest);
    registerPacketHandler(typeid(StoreRequest),
                         (PacketHandlerPtr)&Cache::handle_DataRequest);
    registerPacketHandler(typeid(Response),
                         (PacketHandlerPtr)&Cache::handle_Response);
    registerPacketHandler(typeid(RawFlushRequest),
                         (PacketHandlerPtr)&Cache::handle_RawFlushRequest);
    registerPacketHandler(typeid(CancelRequestsRequest),
                         (PacketHandlerPtr)&Cache::handle_CancelRequestsRequest);
    registerPacketHandler(typeid(InvalidateRequest),
                         (PacketHandlerPtr)&Cache::handle_InvalidateRequest);
    registerPacketHandler(typeid(VerifyRequest),
                         (PacketHandlerPtr)&Cache::handle_VerifyRequest);
    registerPacketHandler(typeid(UpdateRequest),
                         (PacketHandlerPtr)&Cache::handle_UpdateRequest);
    registerPacketHandler(typeid(QuiesceRequest),
                         (PacketHandlerPtr)&Cache::handle_QuiesceRequest);
    registerPacketHandler(typeid(QuiesceResponse),
                         (PacketHandlerPtr)&Cache::handle_QuiesceResponse);
    registerPacketHandler(typeid(RawMemoryRequest),
                         (PacketHandlerPtr)&Cache::handle_RawMemoryRequest);
}

Cache::~Cache () {
    if (global_sim->cfg.shutdown_asserts) {
        ASSERT(stalledLoad == NULL);

        if (stalledSnoopResponse->getLength() != 0) {
            // TODO: explain the following comment
            // there can be pending response to eviction requests.
            // there shouldn't be ones for load request and line flush request.
            while (!stalledSnoopResponse->empty()) {
                SnoopResponse* snr = stalledSnoopResponse->remove();
                Request* req = snr->getRequest();
                CAST_ASSERT(StoreRequest*, req);
                delete req;
                delete snr;
            }        
        }        
        ASSERT(stalledSnoopResponse->getLength() == 0);

        if (pendingResponse->getLength() != 0) {
            while (!pendingResponse->empty()) {
                Response* res = pendingResponse->remove();
                Request* req = res->getRequest();
                CAST_ASSERT(StoreRequest*, req);
                delete req;
                delete res;
            }        
        }        
        ASSERT(stalledSnoopResponse->getLength() == 0);

        while (!agingDataRequests->empty()) {
            // TODO: explain the following comment
            // there can be pending eviction requests.
            // there shouldn't be load request and line flush request.
            while (!agingDataRequests->empty()) {
                PacketDelay* pd = agingDataRequests->remove();
                StoreRequest* req = CAST_OR_DIE(StoreRequest*, pd->request);
                delete req;
                FREE(pd);
            }        
        }     

        while (!mshrs->empty()) {
            MSHR* mshr = mshrs->front();
            mshrs->pop_front();
            delete mshr->victimEntry;
            delete mshr;
        }
    }

    delete blockedLoad;
    delete stalledSnoopResponse;
    delete pendingResponse;

    delete agingDataRequests;

    // Cannot assert this because test_pthread_kill fails. I assume it
    // is because that when the thread is killed the associated
    // processor is halted and it will no longer clear up its
    // canceledLoadRequests.
    // 
    // ASSERT(canceledLoadRequests->empty());
    for (List<LoadRequest*>::iterator iter = canceledLoadRequests->begin();
         iter != canceledLoadRequests->end(); ++iter) {
        delete ((LoadRequest*)(*iter));
    }

    delete canceledLoadRequests;
    delete mshrs;

    hash->clear();
    delete hash;
    // just come after hash deletion, sicne hash uses cacheLog for output
    delete cacheLog;

    delete protoFlags;
}


void Cache::cancelRequests () {
    cacheLog->d("%s:%lli cancelRequests: stalledLoad: %p, blockedLoad: %p, stalledEvict: %p\n",
                getName(),
                global_sim->getSimclock(),
                stalledLoad,
                blockedLoad,
                stalledEvict);

    // clear out the MSHRs
    while (!mshrs->empty()) {
        MSHR* const mshr = mshrs->front();
        mshrs->pop_front();
        cacheLog->d("%s:  MSHR[loadRequest: %0llx [%p], victimEntry: %0llx [%p]]\n",
                    getName(),
                    mshr->loadRequest->getAddress(),
                    mshr->loadRequest,
                    mshr->victimEntry->getAddress(),
                    mshr->victimEntry);

        // we can cancel the load request if it hasn't hit the wire
        // yet, otherwise we wait to delete it
        if (mshr->loadRequest == stalledLoad) {
            delete stalledLoad;
            stalledLoad = NULL;
        } else if (mshr->loadRequest == blockedLoad) {
            delete blockedLoad;
            blockedLoad = NULL;
        } else {
            canceledLoadRequests->push_back(mshr->loadRequest);
        }

        if (mshr->victimEntry->location == NULL) {
            // our responsibility
            delete mshr->victimEntry;
        }

        delete mshr;
    }

    // we're not waiting for lower levels anymore...
    bktStall->unvote();

    if (stalledEvict) {
        cacheLog->d("%s:%lli cancelRequests: stalled evict, but letting it finish\n",
                    getName(),
                    global_sim->getSimclock());
    }
}

bool Cache::stalled (Packet* r) {
    if (stalledLoad != NULL ||
        blockedLoad != NULL ||
        stalledEvict != NULL)
    {
        bktUnavailable->vote();
        // blocking cache.
        return true;
    }
    bktUnavailable->unvote();

    lastAccessClock = global_sim->getSimclock();
    return false;
}

bool Cache::visitUpdate (VA addr, CacheEntry*& e, void* data) {
    ASSERT(e->flags->isValid());
    ASSERT(e->getAddress() == addr);

    bool isSame = true;

    for (uint i = 0; i < e->getBlockSize()/WORD_SIZE; i++) {
        if (((uint32*)e->data)[i] != *(ADDR_UINT32STAR(addr) + i)) {
            isSame = false;
            break;
        }
    }

    if (!isSame) {
        Logger* cacheLog = e->location->getLogger();    
        Entity* owner = e->location->getOwner();
        cacheLog->d("%s: %0llx UPDATE\n", owner->getName(), addr);
                       
        LineMask mask = e->flags->getDirtyMask();
        cacheLog->d("%s:  CEntry: value(", owner->getName());     
        for (uint i = 0; i < e->getBlockSize()/WORD_SIZE; i++) {
            cacheLog->d("%08x[%d] ", *(((uint*)e->data) + i), (uint)mask.get(i));
        }
        cacheLog->d(")\n");   

        cacheLog->d("%s:  Memory: value(", owner->getName());           
        for (uint i = 0; i < e->getBlockSize()/WORD_SIZE; i++) {
            cacheLog->d("%08x[%d] ", *(ADDR_UINT32STAR(addr) + i), (uint)mask.get(i));
        }
        cacheLog->d(")\n");  

        memcpy(e->data, ADDR_UINT32STAR(addr), e->getBlockSize());
    }
    
    return true;
}

bool Cache::visitVerify (VA addr, CacheEntry*& e, void* data) {
    ASSERT(e->getAddress() == addr);

    VerifyRequest* v = (VerifyRequest*)data;

    if (!Memory::cmpMemory((uint32*)e->data,
                           ADDR_UINT32STAR(addr),
                           e->getBlockSize(),
                           e->flags->getValidMask(),
                           true))
    {
        v->failed = true;
    }

    return true;
}

bool Cache::visitInvalidate (VA addr, CacheEntry*& e, void* data) {
    ASSERT(e->getAddress() == addr);
    
    InvalidateRequest* ir = (InvalidateRequest*)data;
    if ((ir->getLowerBound() == 0 && ir->getUpperBound() == 0) ||
        (ir->getLowerBound() <= (addr + e->getBlockSize()) && 
         addr < ir->getUpperBound()))
    {
        Logger* const cacheLog = e->location->getLogger();
        Entity* const owner    = e->location->getOwner();
        cacheLog->d("%s: INVALIDATE %0llx   ",
                    owner->getName(),
                    e->flags->getAddress());
        cacheLog->debugHex(e->data, e->getBlockSize()/WORD_SIZE);

        return false;
    }
    return true;
}

bool Cache::visitRawFlush (VA addr, CacheEntry*& e, void* v) {
    ASSERT(e->getAddress() == addr);
    RawFlushRequest* rfr = (RawFlushRequest*)v;

    if (e->flags->isDirty() &&
        rfr->inBounds(e->getAddress(), 
                      e->getBlockSize())) 
    {
        Logger* cacheLog = e->location->getLogger();
        Entity* owner    = e->location->getOwner();
        cacheLog->d("%s: %0llx RAWFLUSH\n", owner->getName(), addr);

        LineMask mask = e->flags->getDirtyMask();
        cacheLog->d("%s:  CEntry: value(", owner->getName());     
        for (uint i = 0; i < e->getBlockSize()/WORD_SIZE; i++) {
            cacheLog->d("%08x[%d] ", *(((uint*)e->data) + i), (uint)mask.get(i));
        }
        cacheLog->d(")\n");
        
        cacheLog->d("%s:  Memory: value(", owner->getName());
        for (uint i = 0; i < e->getBlockSize()/WORD_SIZE; i++) {
            cacheLog->d("%08x[%d] ", *(ADDR_UINT32STAR(addr) + i), (uint)mask.get(i));
        }
        cacheLog->d(")\n");

        Memory::copyMemory(ADDR_UINT32STAR(addr),
                           e->data,
                           e->getBlockSize(),
                           e->flags->getDirtyMask(),
                           true);  
    }
    return true;
}

Result Cache::handle_CancelRequestsRequest (Packet* r) {
    cacheLog->d("%s:%lli CancelRequestsRequest\n",
                getName(),
                global_sim->getSimclock());


    cancelRequests();
    return routePacket(r);
}

Result Cache::handle_RawFlushRequest (Packet* r) {
    RawFlushRequest* rfr = CAST_OR_DIE(RawFlushRequest*, r);

    // let lower caches flush to memory first.
    if (r->getDestination() != this) {
        Result p = routePacket(r); // its dest should be MainMemory
        ASSERT(p == success);
    }

    cacheLog->d("%s:%lli RawFlushRequest(%llx,%d)\n",
                getName(),
                global_sim->getSimclock(),
                rfr->getStart(),
                rfr->getLength());

    if (isSharedCache()                                 && 
        lastRawFlushTime   == global_sim->getSimclock() &&
        lastRawFlushStart  == rfr->getStart()           &&
        lastRawFlushLength == rfr->getLength())
    {
        cacheLog->d("%s:%lli the shared cache has already flushed\n",
                    getName(),
                    global_sim->getSimclock());   
        return success;
    }
    
    // you probably want to call some variant of hash->Cache::visitRawFlush
    // inside hookRawFlush...
    hookRawFlush(rfr);

    /* 
       jw : we record the current time to make sure that if an
       invalidate request is issued, it should be preceded by raw
       flush request to make sure that we don't invalidate dirty lines
       w/o flushing them to memory.

       we also record the start and length so if we get two flushes in
       the same cycle we won't ignore the second on a shared cache.
       this happens during _exit syscall since we halt the processor
       which causes a rest which flushes the top of stack, while the
       _exit also does a raw flush itself to make sure all state is
       moved from all caches to memory.
    */
    lastRawFlushTime   = global_sim->getSimclock();
    lastRawFlushStart  = rfr->getStart();
    lastRawFlushLength = rfr->getLength();
        
    return success;
}

Result Cache::handle_VerifyRequest (Packet* r) {
    VerifyRequest* vr = CAST_OR_DIE(VerifyRequest*, r);
    cacheLog->d("%s:%lli VerifyRequest ",
                getName(),
                global_sim->getSimclock());

    hash->visit(&Cache::visitVerify, (void*)r);

    cacheLog->d("%s: VerifyRequest: %s\n",
                getName(),
                vr->failed ? "failed" : "passed");

    if (r->getDestination() != this) {
        Result p = routePacket(r);
        ASSERT(p == success);
    }
    return success;
}

Result Cache::handle_RawMemoryRequest (Packet* r) {
    RawMemoryRequest* rmr = CAST_OR_DIE(RawMemoryRequest*, r);

    // make a fake mr...
    MemoryRequest* mr = NEW MemoryRequest(rmr->getAddress(), NULL, NULL, NULL, 0);
    List<CacheEntry*>* list = retrieve(mr);
    delete mr;

    if (!list->empty()) {
        memcpy(rmr->getData(),
               (*(list->begin()))->data,
               global_sim->cfg.blocksize);
    } else {
        // send it down, b/c we dont have it...
        Result p = routePacket(r);
        ASSERT(p == success);
    }
    delete list;
    return success;
}

Result Cache::handle_UpdateRequest (Packet* r) {
    cacheLog->d("%s:%lli UpdateRequest\n",
                getName(),
                global_sim->getSimclock());

    UpdateRequest* ur = CAST_OR_DIE(UpdateRequest*, r);

    // you probably want to call some variant of hash->Cache::visitUpdate
    // inside hookUpdate...
    hookUpdate(ur);
   
    if (r->getDestination() != this) {
        Result p = routePacket(r);
        ASSERT(p == success);
    }
    return success;
}

void Cache::hookUpdate (UpdateRequest* ir) {
    hash->visit(&Cache::visitUpdate, (void*)NULL);
}

Result Cache::handle_InvalidateRequest (Packet* r) {
    InvalidateRequest* ir = CAST_OR_DIE(InvalidateRequest*, r);
    cacheLog->d("%s:%lli InvalidateRequest [0x%llx, 0x%llx]\n",
                getName(),
                global_sim->getSimclock(),
                ir->getLowerBound(),
                ir->getUpperBound());

    invalidate(ir);

    // pass it on
    if (r->getDestination() != this) {
        return routePacket(r);
    } else {
        return success;
    }
}

void Cache::invalidate (InvalidateRequest* ir) {
    // invalidate in the hash
    hash->visit(&Cache::visitInvalidate, (void*)ir);

    // if range is infinite then we should have clobbered everything
    if ((ir->getLowerBound() == 0) && (ir->getUpperBound() == 0)) {
        ASSERT(hash->getLength() == 0);
    }

    invalidateDataRequests(ir);
}

void Cache::invalidateDataRequests (InvalidateRequest* ir) {
    for (List<PacketDelay*>::iterator iter = agingDataRequests->begin();
         iter != agingDataRequests->end(); iter++)
    {
        DataRequest* const bdr = CAST_OR_DIE(DataRequest*, (*iter)->request);

        if (IS_A(StoreRequest*, bdr) &&
            ir->isInRange(bdr->getAddress()))
        {            
            // a cache line with dirty data is to be invalided
            // before flush. check isa implementation.
            if (lastRawFlushTime != global_sim->getSimclock()) {
                ASSERT(false);
            } else {
                // we've already flushed data and the invalidation will make sure
                // that there will not be a cache line with old data. no need for eviction.
                cacheLog->d("%s: INVALIDATION FROM DATA REQUEST:(%0llx) ",
                            getName(),
                            bdr->getAddress());
                cacheLog->debugHex((uint*)bdr->getData(), blockSize/WORD_SIZE);

                iter = agingDataRequests->erase(iter);
                if(routePacket(NEW Response(bdr)) != success) {
                    ASSERT(0);
                }
            }
        }
    }

    // then eviction buffer
    if (stalledEvict != NULL && ir->isInRange(stalledEvict->getAddress())) {
        // a cache line with dirty data is to be invalided
        // before flush. check isa implementation.
        if (lastRawFlushTime != global_sim->getSimclock()) {
            ASSERT(false);
        } else {
            // we've already flushed data and the invalidation will make sure
            // that there will not be a cache line with old data. no need for eviction.
            cacheLog->d("%s: INVALIDATION FROM EVICTION REQUEST:(%0llx) ",
                        getName(),
                        stalledEvict->getAddress());
            cacheLog->debugHex((uint*)stalledEvict->getData(), blockSize/WORD_SIZE);

            delete stalledEvict;
            stalledEvict = NULL;
        }
    }
}

Result Cache::handle_MemoryRequest (Packet* r) {
    DataRequest* dr = (DataRequest*)r;

    if (stalled(r)) {
        return stall;
    }
    
    if (IS_A(StoreRequest*, r)) {
        cacheLog->d("%s:%lli:%0llx %s STORE value (",
                    dr->getProcessor()->getName(),
                    global_sim->getSimclock(),
                    dr->getAddress(),
                    getName());
          
        for (uint i = 0; i < dr->getDataSize() / WORD_SIZE; i++) {
            if (i != 0) {
                cacheLog->d(" ");
            }
            cacheLog->d("%08x", *(((uint*)dr->getData()) + i));
        }
        cacheLog->d(")\n");                   
    } else if (IS_A(LoadRequest*, r)) {
        cacheLog->d("%s:%lli:%0llx %s LOAD\n",
                    dr->getProcessor()->getName(),
                    global_sim->getSimclock(),
                    dr->getAddress(),
                    getName());
    }

    List<CacheEntry*>* list = hash->retrieve(blockAddr(dr->getAddress()));

    List<CacheEntry*>::iterator it = list->begin();
    for (; it != list->end(); it++) {
        CacheEntry* walk = *it;
        cacheLog->d("%s:  %0llx %s\n",
                    getName(),
                    walk->getAddress(),
                    walk->flags->str());
    }
    statAccesses->increment(1);
    Result result = handleAccess(dr, list);

    delete list;
    return result;
}

Result Cache::handleStoreHit (StoreRequest* const sr, CacheEntry* const entry) {
    statHits->increment(1);

    ASSERT((sr->getAddress() & (WORD_SIZE - 1)) == 0);

    entry->touch();
    entry->flags->setDirty(true);        
    uint* const data = &entry->data[wordOffset(sr->getAddress())];
    memcpy(data, sr->getData(), sr->getDataSize());

    return routePacket(NEW Response(sr,1));
}

Result Cache::handleLoadHit (LoadRequest* const lr, CacheEntry* const entry) {
    uint* const data = &entry->data[wordOffset(lr->getAddress())];

    statHits->increment(1);

    ASSERT((lr->getAddress() & (WORD_SIZE - 1)) == 0);

    entry->touch();

    lr->insertData(data, lr->getDataSize());

    cacheLog->d("%s:  HIT value(", getName());
    for (uint i = 0; i < lr->getDataSize() / WORD_SIZE; i++) {
        if (i != 0) {
            cacheLog->d(" ");
        }
        cacheLog->d("%08x", *(((uint*)lr->getData()) + i));
    }
    cacheLog->d(")\n");

    return routePacket(NEW Response(lr));
}

CacheEntry* Cache::assignVictimLine (MemoryRequest const* const r) {
    VA const addr = blockAddr(r->getAddress());

    if (!isAssocSetFull(addr)) {
        // space left in the associativity set, create a new line
        CacheEntry* const victim = NEW CacheEntry(protoFlags->newInstance(addr),
                                                  r->getProcessor());

        cacheLog->d("%s:%lli:%s VICTIM ENTRY IS CREATED for (%0llx)\n",
                    getName(),
                    global_sim->getSimclock(),
                    r->getSource()->getName(),
                    addr);

        return victim;
    }

    // fetch all of the entries in the associativity set
    List<CacheEntry*>* const set = hash->retrieveSet(addr);
    ASSERT(set->size() > 0);

    CacheEntry* const victim = getBestVictim(set);
    ASSERT(victim != NULL);

    delete set;

    cacheLog->d("%s:%lli:%s VICTIM IS SELECTED(%0llx %s) for (%0llx)\n",
                r->getSource()->getName(),
                global_sim->getSimclock(),
                getName(),
                victim->getAddress(),
                victim->flags->str(),
                addr);

    hash->remove(victim);

    return victim;
}

CacheEntry* Cache::getBestVictim (List<CacheEntry*> const* const list) {
    return list->peek();
}


LoadRequest* Cache::makeRefillRequest (DataRequest* dr) {
    LoadRequest* lr = NEW LoadRequest(blockAddr(dr->getAddress()),
                                      dr->getProcessor(),
                                      this,
                                      global_sim->getMemory(),
                                      blockSize);
                                    
    lr->initiatingRequest = dr;
    lr->setNonSpeculative(dr->isNonSpeculative());

    return lr;
}

uint Cache::numVictimsInSet (VA const addr) const {
    uint result = 0;
    for (List<MSHR*>::const_iterator iter = mshrs->begin(); iter != mshrs->end(); ++iter) {
        if (setMatch(addr, (*iter)->loadRequest->getAddress())) {
            ++result;
        }
    }
    return result;
}

bool Cache::isInMSHR (VA const addr) const {
    for (List<MSHR*>::const_iterator iter = mshrs->begin(); iter != mshrs->end(); ++iter) {
        if (blockMatch(addr, (*iter)->loadRequest->getAddress())) {
            return true;
        }
    }
    return false;
}


bool Cache::canMiss (VA const addr) const {
    // verify that we can allocate an MSHR
    if (mshrs->size() >= maxMSHRs) {
        return false;
    }
    // verify that the promised victim entries won't exceed
    // the set associativity of the line for addr if another
    // one is added
    if (maxMSHRs > assoc && numVictimsInSet(addr) + 1 > assoc) {
        return false;
    }

    // if there is an outstanding miss to the address, let the following
    // requests to wait until the precedent miss is handled.
    if (isInMSHR(addr)) {
        return false;
    }
    return true;
}

bool Cache::isAssocSetFull (VA const addr) {
    struct CHAvailable avail = hash->spaceAvailable(addr);

    uint const reserved = numVictimsInSet(addr);
    if (avail.associativity > reserved) {
        return false; // there's some associativity left...
    }

    if (avail.victimCache > reservedVCs) {
        reservedVCs++;
        return false; // there's space in the VC; reserve it
    }
    return true;
}

MSHR* Cache::createMSHR (DataRequest* dr, CacheEntry* ve) {
    ASSERT(!isInMSHR(dr->getAddress()));
    MSHR* const mshr = NEW MSHR(makeRefillRequest(dr), ve);
    mshrs->push_back(mshr);
    ASSERT(mshrs->size() <= maxMSHRs);
    return mshr;
}

void Cache::routeOrEnqueueNewRefillRequest (DataRequest* dr, CacheEntry* ve) {
    if (isForNoFetchAtWriteMiss(dr)) {
        handleNoFetchAtWriteMiss(dr, ve);
    } else {
        routeOrEnqueue(createMSHR(dr, ve)->loadRequest);
    }
}

// this method is intended for no-fetch-at-write-miss
void Cache::handleNoFetchAtWriteMiss (DataRequest* dr, CacheEntry* ve) {
    cacheLog->d("%s:  NO FETCH AT WRITE MISS: %0llx \n",
                getName(),
                dr->getAddress());

    if (isSharedCache()) {
        LoadRequest* lr = createMSHR(dr, ve)->loadRequest;
        pendingResponse->add(NEW Response(lr));

        return;
    }

    StoreRequest* sr = CAST_OR_DIE(StoreRequest*, dr);

    // copy the data...
    Memory::copyMemory((uint32*)ve->data,
                       (const uint32*)sr->getData(),
                       sr->getDataSize(),
                       LineMask::ALL_TRUE,
                       true); 

    // copy the flags...
    if (ve->location != NULL) {
        ASSERT(ve->location == hash);
        ASSERT(!ve->flags->isDirty());
        ASSERT(ve->flags->isValid());

        hash->remove(ve);
    }
    if (ve->flags) {
        // this could be b/c im resuing an entry or b/c i created a new
        // victim line...either way, get rid of the flags we have...
        delete ve->flags;
    }

    ASSERT(dr->getFlags());
    ve->flags = dr->getFlags()->clone();

    hash->insert(ve->getAddress(), ve);

    // verify the flags...
    ASSERT(ve->flags->isValid());

    Result r = routePacket(makeResponse(dr));
    ASSERT(r == success);
}

bool Cache::isForNoFetchAtWriteMiss(DataRequest* dr) {
    return (isSharedCache()) && IS_A(StoreRequest*, dr);
}

Result Cache::handleMissNoevict (DataRequest* dr, CacheEntry* ve) {
    // this creates the MSHR, creates and sends a refill LoadRequest
    routeOrEnqueueNewRefillRequest(dr, ve);
    return success;
}

Result Cache::handleMiss (DataRequest* dr, CacheEntry* ve) {
    // at this point ve is not yet in an MSHR

    ASSERT(ve != NULL);
    ASSERT(canMiss(ve->getAddress()));

    statMisses->increment();
    cacheLog->d("%s:  MISS\n", getName());

    if (!ve->flags->isValid()) {
        // nothing to evict
        return handleMissNoevict(dr, ve);
    } 

    // at this point, we know we have to evict a line.
    cacheLog->d("%s:  %0llx EVICTION\n", getName(), ve->getAddress());

    StoreRequest* dataWB = NULL;
    if (ve->flags->isDirty()) {
        cacheLog->d("%s:%lli:%0llx %s VICTIM ENTRY WRITEBACK: (%s)\n",
                    dr->getSource()->getName(),
                    global_sim->getSimclock(),
                    ve->getAddress(),
                    getName(),
                    ve->flags->str());

        dataWB = NEW StoreRequest(ve->getAddress(),
                                  dr->getProcessor(),
                                  this,
                                  global_sim->getMemory(),
                                  blockSize);
        dataWB->setWritebackType(WB_EVICTION);
        ((StoreRequest*)dataWB)->initiatingRequest = NULL;
        dataWB->insertData(&ve->data, blockSize);
        dataWB->setFlags(ve->flags->clone());
        cacheLog->d("%s flags: %x\n", getName(), (uint)dataWB->getFlags());

        cacheLog->d("%s:  ", getName());
        cacheLog->debugHex((uint*)ve->data, blockSize/WORD_SIZE);
    }

    // any data in the victim entry has been copied into
    // a StoreRequest that is now embedded in er, so we
    // don't need the data in the victim entry any more
    ve->flags->setValid(false);

    return handleMissEvict(dr, ve, dataWB);    
}

Result Cache::handleMissEvict (DataRequest* dr,
                               CacheEntry* ve,
                               StoreRequest* dataWB)
{
    // this creates the MSHR, creates and sends a refill LoadRequest
    routeOrEnqueueNewRefillRequest(dr, ve);

    if (dataWB != NULL) {
        // outstandingEvicts weirdness: so if this is going from the
        // L1 to the L2 and routePacket() comes back in one cycle,
        // then the evict will be done in one cycle and it will dec
        // outsandingEvicts---so we have to ++ first then -- if we end
        // up stalling (outstandingEvicts only counts SENT evicts)...
        outstandingEvicts++;
        if (routePacket(dataWB) == stall) {
            decOutstandingEvicts();
            enqueueStalledRequest(dataWB);
        }
    }

    return success;
}

void Cache::hookResponse (Response* const resp) {
    // nothing here
}

Result Cache::handle_Response (Packet* r) {
  //printf("Cache::handle_Response: START\n");
    Response* resp = CAST_OR_DIE(Response*, r);
    Request* req = resp->getRequest();

    // first see if this was a cancelled request
    for (List<LoadRequest*>::iterator iter = canceledLoadRequests->begin();
         iter != canceledLoadRequests->end();
         ++iter)
    {
        if (req == *iter) {
            LoadRequest* lr = CAST_OR_DIE(LoadRequest*, req);
            cacheLog->d("%s:%lli: %0llx [%p] received spurious load response!\n",
                        getName(),
                        global_sim->getSimclock(),
                        lr->getAddress(),
                        req);
            delete req;
            canceledLoadRequests->erase(iter);
            delete r;
            // we're done waiting for lower level...
            bktStall->unvote();

           return success;
        }
    }
    // make sure this isn't growing out of control
    ASSERT(canceledLoadRequests->size() < 64);

    // next, check whether the request was processed successfully
    hookResponse(resp);

    if (IS_A(LoadRequest*, req)) {
        LoadRequest* lr = (LoadRequest*)req;
        VA const lrBlockAddr = blockAddr(lr->getAddress());

        // we're done waiting for lower level...
        bktStall->unvote();

        cacheLog->d("%s:%lli:%0llx %s REFILL:\n",
                    lr->getSource()->getName(),
                    global_sim->getSimclock(),
                    lr->getAddress(),
                    name);

        MSHR* mshr = NULL;
        for (List<MSHR*>::iterator iter = mshrs->begin(); iter != mshrs->end(); ++iter) {
            if ((*iter)->loadRequest == lr) {
                mshr = *iter;
                // we remove the mshr entry at the end of this method to have the hook
                // methods to distinquish if the CacheEntry is updated after refill.
                //mshrs->erase(iter);
                break;
            }
        }

        // there should be a matching load request for the response.
        ASSERT(mshr != NULL);
        
        CacheEntry* const ve = mshr->victimEntry;

        hookPreLoadRefill(lr, mshr);

        DataRequest* ir = CAST_OR_DIE(DataRequest*, lr->initiatingRequest);    

        // make a response
        Response* res = makeResponse(ir);
      
        cacheLog->d("%s:  ", getName());
        cacheLog->debugHex((uint*)lr->getData(), blockSize/WORD_SIZE);
        
        // if the victim is currently a different valid line it
        // should not contain dirty data
        if (ve->location != NULL && ve->getAddress() != lrBlockAddr) {
            ASSERT(!ve->flags->isDirty());
            ASSERT(ve->flags->isValid());
            ASSERT(ve->location == hash);
            
            hash->remove(ve);
        }
        
        if (ve->flags == NULL ||
            ve->flags->isValid() == false)
        {
            // clear out the flags just to make sure there's
            // no hidden state around...
            if (ve->flags) {
                delete ve->flags;
            }
            if (lr->getFlags()) { // did we get flags from the L2?
                ASSERT(Simulator::hasPrivateL2());
                ASSERT(lr->getFlags()->getAddress() ==
                       lrBlockAddr);

                ve->flags = lr->getFlags()->clone();
                cacheLog->d("%s:  COPYING FLAGS FROM L2\n",
                            getName());
            } else {
                ve->flags = protoFlags->newInstance(lrBlockAddr);
            }
        } else {
            // this must be a valid line that we're refilling
            // part of...
            ASSERT(ve->flags);
            ASSERT(ve->flags->isValid());
            ASSERT(lrBlockAddr == ve->getAddress());
        }
           
        ve->flags->setValid(true);
            
        // only copy over the words whose dirty bit is _not_ set
        Memory::copyMemory((uint32*)ve->data,
                           (const uint32*)lr->getData(),
                           lr->getDataSize(),
                           // if its from the L2, dont use the dirtymask...
                           lr->getFlags() ? LineMask::ALL_FALSE : ve->flags->getDirtyMask(),
                           false); 

        // this will update the flags
        hookLoadRefill(lr, mshr);

        if (ve->location == NULL) {
            hash->insert(ve->getAddress(), ve);
        }

        // refill is done. process the request.
        // the request is on a word if the request is from a processor.
        // the request is on a block if the request is from a cache.
        if (ir->getDataSize() == WORD_SIZE) {
            uint* data = &ve->data[wordOffset(ir->getAddress())];

            if (IS_A(LoadRequest*, ir)) {
                uint someData = *data;
                ir->setWord(someData);    

                cacheLog->d("%s:  %0llx LOAD value(%08x)\n",
                            getName(),
                            ir->getAddress(),
                            someData); 
            } else if (IS_A(StoreRequest*, ir)) {
                // if we're doing a store, actually store it in the cache...
                *data = *(uint32*)(ir->getData());
                ve->flags->setDirty(true);

                cacheLog->d("%s:  %0llx STORE value(%08x)\n",
                            getName(),
                            ir->getAddress(),
                            *(uint*)((DataRequest*)ir)->getData());
            } else {
                ASSERT(false);
            }
        } else {
            // here we assume that the cache line size for L1 and L2 are
            // the same.
            //
            ASSERT(((DataRequest*)ir)->getDataSize() == blockSize);

            if (IS_A(LoadRequest*, ir)) {
                ir->insertData(&ve->data, blockSize);  

                cacheLog->d("%s:  %0llx LOAD ",
                            getName(),
                            ir->getAddress()); 
                cacheLog->debugHex((uint*)ir->getData(),
                                   blockSize/WORD_SIZE);
            } else if (IS_A(StoreRequest*, ir)) {
                // if we're doing a store, actually store it in the cache...
                Memory::copyMemory((uint32*)ve->data,
                                   (const uint32*)ir->getData(),
                                   ir->getDataSize(),
                                   ir->getMask(),
                                   true); 
                ve->flags->setDirty(true);

                cacheLog->d("%s:  %0llx STORE ",
                            getName(),
                            ir->getAddress()); 
                cacheLog->debugHex((uint*)ve->data, blockSize/WORD_SIZE);
            } else {
                ASSERT(false);
            }                
        }

        // this means the processor's request is done...
        if (ve->isInVictimCache()) {
            ASSERT(reservedVCs > 0);
            reservedVCs--;
        }
        mshrs->remove(mshr);
        delete mshr;
        routePacket(res);
    } else if (IS_A(StoreRequest*, req)) {
        StoreRequest* sr = (StoreRequest*)req;
        // these are eviction requests...

        if (sr->getSource() != this) {
            Result r = routePacket(resp);
            ASSERT(r == success);
            return success;
        } else {
            cacheLog->d("%s:%lli:%0llx %s EVICTION:DONE\n",
                        sr->getProcessor()->getName(),
                        global_sim->getSimclock(),
                        sr->getAddress(),
                        name);
            decOutstandingEvicts();
        }
        // great its done, move on w/ your life... (FALLTHROUGH)
    } else {
        cacheLog->w("X:%lli: %s Unknown response: %s(%s)\n",
                    global_sim->getSimclock(),
                    name,
                    r->toString(),
                    typeid(*r).name());
        ASSERT(false);
    }

    delete r;
    delete req;
    //printf("Cache::handle_Response: DONE\n");
    return success;
}

Response* Cache::makeResponse(DataRequest* r) {
    if (IS_A(LoadRequest*, r)) {
        return NEW Response(r);
    } else if (IS_A(StoreRequest*, r)) {
        return NEW Response(r, 1);    
    } else {
        ASSERT(false);
        return NULL;
    }  
}

Result Cache::handle_DataRequest (Packet* r) {
    ASSERT(IS_A(StoreRequest*, r) ||
           IS_A(LoadRequest*, r));
    
    if (IS_A(StoreRequest*, r)) {
        StoreRequest* sr = (StoreRequest*)r;
        if (sr->isFlushed()) {
            // this packet was already handled by a RawFlushRequest...
            // just send back a response saying we handled it
            cacheLog->d("  RAWFLUSH IGNORED AT CACHE cache=%s (%0llx)\n",
                        getName(),
                        sr->getAddress());
            Response* res = NEW Response(sr, 1);
            Result result = routePacket(res);
            ASSERT(result == success);
            return result;
        } 
    }
    
    if (delay == 0) {
        return handle_MemoryRequest(r);
    } else {
        // if the delay(hittime) is non-zero, defer its delivery.
        PacketDelay* rd = (PacketDelay*)CALLOC(1, sizeof(PacketDelay));
        rd->request = (DataRequest*)r;
        rd->alarm = global_sim->getSimclock() + delay;

        agingDataRequests->add(rd);
        
        cacheLog->d("%s:%lli:%0llx %s REQUEST INTO INPUT BUFFER (%s)\n",
                    ((DataRequest*)r)->getSource()->getName(),
                    global_sim->getSimclock(),
                    ((DataRequest*)r)->getAddress(),
                    name,
                    IS_A(StoreRequest*, r) ? "(ST)":"(LD)");        
    }

    return success;
}

Result Cache::handle_QuiesceRequest (Packet* r) {
    quiesceLog->d("%s:%lli: Cache::handle_QuiesceRequest\n", getName(), global_sim->getSimclock());
    if (quiesce) {
        return handleDuplicateQuiesceRequest(r);
    }    

    ASSERT(quiesceRequest == NULL);
    
    quiesce = true;
    
    if (isReadyForQuiesce()) {
        sendQuiesceRequest((QuiesceRequest*)r);
    } else {
        quiesceRequest = (QuiesceRequest*)r;
    }
    
    return success;
}

bool Cache::isReadyForQuiesce () {
    return !stalled(NULL) && outstandingEvicts == 0;
}

Result Cache::handleDuplicateQuiesceRequest (Packet* r) {
    // a shared cache receives a multiple quiesce request.
    // return the request immediately except the first.
    if (!isSharedCache()) {
        ASSERT(quiesce == false);
    }
 
    QuiesceRequest* qreq = CAST_OR_DIE(QuiesceRequest*, r);
    QuiesceResponse* qr = NEW QuiesceResponse(qreq);
    Result res = routePacket(qr);
    ASSERT(res == success);
    return success;
}

bool Cache::isSharedCache () {
    return (strstr(name, "SHARED") != NULL);
}

Result Cache::handle_QuiesceResponse (Packet* r) {
    quiesceLog->d("%s:%lli: Cache::handle_QuiesceResponse\n", getName(), global_sim->getSimclock());

    quiesce = false;
    quiesceRequest = NULL;    

    Result res = routePacket(r);
    ASSERT(res == success);
    
    return success;
}

void Cache::tick () {
    if (quiesce) {
        if (isReadyForQuiesce()) {
            if(quiesceRequest != NULL) {
                QuiesceRequest* rq = quiesceRequest;
                quiesceRequest = NULL;
                sendQuiesceRequest(rq);
            }
        } else {
            quiesceLog->d("%s:%lli stalled(%i) outstandingEvicts(%i)\n",
                          getName(),
                          global_sim->getSimclock(),
                          stalled(NULL),
                          outstandingEvicts);
        }
    }

    // handle the stall of the outgoing messages 
    // retry sending requests
    if (stalledLoad != NULL) {
        if (routePacket(stalledLoad) == success) {
            cacheLog->d("%s:%lli:%0llx %s STALLED LOAD ISSUED\n",
                        stalledLoad->getSource()->getName(),
                        global_sim->getSimclock(),
                        stalledLoad->getAddress(),
                        name);            
            stalledLoad = NULL;
        }   
    }
    
    if (stalledEvict != NULL) {
        if (routePacket(stalledEvict) == success) {
            // this could be a stalled evict we're holding in the L2 for the L1
            // in that case, the L1 already has an outstanding evict counter
            // waiting for it...
            if (stalledEvict->getSource() == this) {
                outstandingEvicts++;
            }
            cacheLog->d("%s:%lli:%0llx %s STALLED EVICTION ISSUED\n",
                        stalledEvict->getSource()->getName(),
                        global_sim->getSimclock(),
                        stalledEvict->getAddress(),
                        name); 
            stalledEvict = NULL;
        }        
    }

    // we process 1 data request at a cycle
    if (!agingDataRequests->empty() &&
        global_sim->getSimclock() >= agingDataRequests->peek()->alarm)
    {
        PacketDelay* pd = agingDataRequests->remove();
        DataRequest* r = (DataRequest*)pd->request;

        Result ret = handle_MemoryRequest(r);
        
        // we deliver the request in order
        // what if we do out-of-order deliver? next homework it is.
        if (ret == stall) {
            agingDataRequests->push_front(pd);            
        } else {
            // the request is delivered whether it succeeded or failed.
            FREE(pd);
        }
    }

    if (!pendingResponse->empty()) {
        Response* res = pendingResponse->remove();

        Result ret = handle(res);
        ASSERT(ret == success);
    }
    

    if (!stalledSnoopResponse->empty()) {
        SnoopResponse* sr = stalledSnoopResponse->remove();

        Result ret = routePacket(sr);
        
        // we deliver the request in order
        // what if we do out-of-order deliver? next homework it is.
        if (ret == stall) {
            stalledSnoopResponse->push_front(sr);            
        } 
    }
}

List<CacheEntry*>* Cache::retrieve (MemoryRequest* mr) {
    List<CacheEntry*>* list = hash->retrieve(blockAddr(mr->getAddress()));
    return list;
}

void Cache::routeOrEnqueue (DataRequest* dr) {
    // ok, from now on, we're waiting for the lower level...
    bktStall->vote();

    if (routePacket(dr) == stall) {
        enqueueStalledRequest(dr);
    }
}

void Cache::enqueueStalledRequest (DataRequest* dr) {
    // if we are L1 talking to L2 then L2 should accept all
    // data requests into its input buffer
    // TODO: nbronson: ASSERT(isLastCache());

    if (IS_A(LoadRequest*, dr)) {
        ASSERT(stalledLoad == NULL);
        stalledLoad = dr;
        cacheLog->d("%s:  %0llx LOAD REQUEST STALL\n",
                    getName(),
                    dr->getAddress());
    } else if (IS_A(StoreRequest*, dr)) {
        ASSERT(stalledEvict == NULL);
        stalledEvict = dr;
        cacheLog->d("%s:  %0llx EVICTION REQUEST STALL\n",
                    getName(),
                    dr->getAddress());
    } else {
        ASSERT(false);
    }
} 

void Cache::enqueueBlockedRequest (DataRequest* dr) {
    ASSERT(blockedLoad == NULL);
    blockedLoad = CAST_OR_DIE(LoadRequest*, dr);
    blockedLoadTime = global_sim->getSimclock();

    cacheLog->d("%s:  %0llx LOAD REQUEST BLOCK\n",
                getName(),
                dr->getAddress());
} 

void Cache::flushBlockedRequests () {
    if (blockedLoad != NULL) {
        cacheLog->d("%s:%lli:%0llx %s FLUSHING BLOCKED REQUEST: %s\n",
                    blockedLoad->getSource()->getName(),
                    global_sim->getSimclock(),
                    blockedLoad->getAddress(),
                    name,
                    blockedLoad->toString());

        enqueueStalledRequest(blockedLoad);
        blockedLoad = NULL;
    }
}

void Cache::decOutstandingEvicts () {
    ASSERT(outstandingEvicts > 0);
    outstandingEvicts--;
}


Result Cache::routeExternal (Packet* r) {
    bool isStoreRequest = (IS_A(StoreRequest*, r));
    
    Result ret = routePacket(r);
    
    if (ret == success && isStoreRequest) {
        ASSERT(outstandingEvicts >= 0);
        outstandingEvicts++;       
    }
    
    return ret;
}


void Cache::hookLoadRefill (LoadRequest* lr, MSHR* mshr) {
    // nothing here
} 

void Cache::hookPreLoadRefill (LoadRequest* lr, MSHR* mshr) {
    // nothing here
} 

void Cache::sendQuiesceRequest (QuiesceRequest* qr) {
    quiesceLog->d("%s:%lli: QUIESCED.\n",
                  name,
                  global_sim->getSimclock());

    Result res = routePacket(qr);
    ASSERT(res == success);  
}

